#include <iostream>
#include <vector>
#include <queue>
//#include <math.h>
using namespace std;

class Solution {
    public:
	int minimumEffortPath(vector<vector<int>> &heights)
	{
		int n = heights.size();
                int m = heights[0].size();
		vector<vector<int>> vis(n, vector<int>(m, 0));
		vector<vector<int>> dis(n, vector<int>(m, INT32_MAX));
		auto cmp = [](auto &a, auto &b) { return a[2] > b[2]; };
		priority_queue<vector<int>, vector<vector<int>>, decltype(cmp)> pq(cmp);
		pq.push({ 0, 0, 0 });
		dis[0][0] = 0;

		vector<int> direct = { -1, 0, 1, 0, -1 };
		while (!pq.empty()) {
			auto e = pq.top();
			pq.pop();
			int row = e[0], col = e[1], w = e[2];
			if (vis[row][col]) {
				continue;
			}
                        vis[row][col] = 1;
                        for(int i = 0; i < 4; i++){
                                int nrow = row + direct[i];
                                int ncol = col + direct[i + 1];
                                if(nrow < n && nrow >= 0 && ncol < m && ncol >= 0 && !vis[nrow][ncol]){
                                        int cost = max(w, abs(heights[row][col] - heights[nrow][ncol]));
                                        if(cost < dis[nrow][ncol]){
                                                dis[nrow][ncol] = cost;
                                                pq.push({nrow, ncol, cost});
                                        }
                                }
                        }
		}
                return dis[n - 1][m - 1];
	}
};

int main()
{
	vector<vector<int>> heights = { { 1, 2, 2 }, { 3, 8, 2 }, { 5, 3, 5 } };
	cout << Solution().minimumEffortPath(heights) << endl;
	return 0;
}